#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char ElementType;

typedef struct TreeNode
{
    ElementType data;
    struct TreeNode *lChild;
    struct TreeNode *rChild;
} TreeNode, *BitTree;

typedef struct QNode
{
    void *data;
    struct QNode *next;
} QNode;

typedef struct Queue
{
    QNode *front;
    QNode *rear;
} Queue;

void InitQueue(Queue &q)
{
    q.front = q.rear = new QNode();
    q.front->next = NULL;
}

bool EmptyQueue(Queue q)
{
    return q.front == q.rear;
}

void EnQueue(Queue &q, void *d)
{
    QNode *node = (QNode *)malloc(sizeof(QNode));
    node->data = d;
    node->next = q.rear->next;
    q.rear->next = node;
    q.rear = node;
}

void *DeQueue(Queue &q)
{
    if (EmptyQueue(q))
    {
        return NULL;
    }
    QNode *tmp_node = q.front->next;
    void *data = tmp_node->data;
    q.front->next = tmp_node->next;
    if (tmp_node->next == NULL)
    {
        q.rear = q.front;
    }
    free(tmp_node);
    return data;
}

// 层次建树
BitTree BuildTree(ElementType *ch, int len)
{
    if (len == 0)
    {
        return NULL;
    }
    BitTree root = (BitTree)malloc(sizeof(TreeNode));
    root->lChild = NULL;
    root->rChild = NULL;
    root->data = ch[0];
    TreeNode *cur_node = root;
    Queue queue;
    InitQueue(queue);
    for (int index = 1; index < len; index++)
    {
        TreeNode *t_node = (TreeNode *)malloc(sizeof(TreeNode));
        t_node->data = ch[index];
        t_node->lChild = NULL;
        t_node->rChild = NULL;
        if (cur_node->lChild != NULL && cur_node->rChild != NULL)
        {
            cur_node = (TreeNode *)DeQueue(queue);
        }
        if (cur_node->lChild == NULL)
        {
            cur_node->lChild = t_node;
        }
        else
        {
            cur_node->rChild = t_node;
        }
        EnQueue(queue, t_node);
    }
    return root;
}

void PreOrderTree(BitTree tree)
{
    if (tree)
    {
        printf("%2c", tree->data);
        PreOrderTree(tree->lChild);
        PreOrderTree(tree->rChild);
    }
}

typedef struct SNode
{
    void *data;
    struct SNode *next;
} SNode, *Stack;

void InitStack(Stack &stack)
{
    stack = (SNode *)malloc(sizeof(SNode));
    stack->next = NULL;
}

bool EmptyStack(Stack stack)
{
    return stack->next == NULL;
}

void StackPush(Stack stack, void *data)
{
    SNode *s_node = (SNode *)malloc(sizeof(SNode));
    s_node->data = data;
    s_node->next = stack->next;
    stack->next = s_node;
}

void *StackPop(Stack stack)
{
    if (EmptyStack(stack))
    {
        return NULL;
    }
    SNode *tmp_node = stack->next;
    void *data = tmp_node->data;
    stack->next = tmp_node->next;
    free(tmp_node);
    return data;
}

// 非递归先序遍历二叉树
void PreOrderTree2(BitTree tree)
{
    Stack stack;
    BitTree treeNode = tree;
    InitStack(stack);
    while (!EmptyStack(stack) || treeNode)
    {
        if (treeNode)
        {
            printf("%c", treeNode->data);
            StackPush(stack, treeNode);
            treeNode = treeNode->lChild;
        }
        else
        {
            treeNode = (TreeNode *)StackPop(stack);
            treeNode = treeNode->rChild;
        }
    }
}

void PreOrderTreeV2(BitTree tree)
{
    if (!tree)
    {
        return;
    }
    printf("\n");
    Stack stack;
    InitStack(stack);
    StackPush(stack, tree);
    while (!EmptyStack(stack))
    {
        TreeNode *node = (TreeNode *)StackPop(stack);
        printf("%2c", node->data);
        if (node->rChild)
        {
            StackPush(stack, node->rChild);
        }
        if (node->lChild)
        {
            StackPush(stack, node->lChild);
        }
    }
    printf("\n");
}

void MidOrderTree(BitTree tree)
{
    if (tree)
    {
        MidOrderTree(tree->lChild);
        printf("%2c", tree->data);
        MidOrderTree(tree->rChild);
    }
}

void MidOrderTreeV2(BitTree tree)
{
    printf("\n");
    Stack stack;
    InitStack(stack);
    while (tree->lChild || tree->rChild || !EmptyStack(stack))
    {
        while (tree->lChild)
        { // 左子树不为空，节点进栈
            StackPush(stack, tree);
            tree = tree->lChild;
        }
        // 左子树为空，打印节点值
        printf("%2c", tree->data);
        if (tree->rChild) // 右子树不为空，赋值为右子树
        {
            tree = tree->rChild;
        }
        else // 右子树为空，出栈
        {
            tree = (TreeNode *)StackPop(stack);
            tree->lChild = NULL;
        }
    }
    if (tree)
    {
        printf("%2c", tree->data);
    }
    printf("\n");
}

void PostOrderTree()
{
}

void PostOrderTreeV2()
{
}

int main()
{
    ElementType ch[] = "abcdefghijklmno";
    BitTree tree = BuildTree(ch, 15);
    printf("-----------preOrderTree-------------------\n");
    PreOrderTree(tree);
    PreOrderTreeV2(tree);
    printf("-----------midOrderTree--------------------\n");
    MidOrderTree(tree);
    MidOrderTreeV2(tree);
    return 0;
}